#include <iostream>
#include <unordered_map>

using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
/*
class Solution {
private:
    unordered_map<Node*, Node*> map;
    void forward(Node* old_node, Node* new_node) {
        if (old_node->next != NULL) {
            auto iter = map.find(old_node->next);
            if (iter == map.end()) {
                Node* next_node = new Node(old_node->next->val, NULL, NULL);
                map.insert(pair<Node*, Node*>{old_node->next, next_node});
                new_node->next = next_node;
                forward(old_node->next, next_node);
            } else {
                new_node->next = iter->second;
            }
        }
        if (old_node->random != NULL) {
            auto iter = map.find(old_node->random);
            if (iter == map.end()) {
                Node* random_node = new Node(old_node->random->val, NULL, NULL);
                map.insert(pair<Node*, Node*>{old_node->random, random_node});
                new_node->random = random_node;
                forward(old_node->random, random_node);
            } else {
                new_node->random = iter->second;
            }
        }
    }
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return NULL;
        }
        Node* new_head = new Node(head->val, NULL, NULL);
        map.insert(pair<Node*, Node*>{head, new_head});
        forward(head, new_head);
        return new_head;
    }
};*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return NULL;
        }
        Node* new_head = new Node(head->val, NULL, NULL);
        unordered_map<Node*, Node*> map;
        map.insert(pair<Node*, Node*>{head, new_head});
        Node* p = new_head;
        Node* q = head->next;
        while (q != NULL) {
            Node* next_node = new Node(q->val, NULL, NULL);
            map.insert(pair<Node*, Node*>{q, next_node});
            p->next = next_node;
            p = p->next;
            q = q->next;
        }
        q = head;
        p = new_head;
        while (q != NULL) {
            if (q->random != NULL) {
                auto iter = map.find(q->random);
                p->random = iter->second;
            }
            p = p->next;
            q = q->next;
        }
        return new_head;
    }
};

int main() {
    Node head(-1, NULL, NULL);
    head.random = &head;
    Solution solution;
    auto new_head = solution.copyRandomList(&head);
    return 0;
}